class Solution:
    _MOD = 10 ** 9 + 7

    def numPermsDISequence(self, s: str) -> int:
        size = len(s) + 1

        if size <= 2:
            return 1

        dp1 = [1]

        for i in range(size - 1):
            dp2 = [0] * (i + 2)

            # 处理下降的情况
            if s[i] == "D":
                for j in range(i + 1):
                    for k in range(j + 1, i + 2):
                        dp2[k] = (dp2[k] + dp1[j]) % self._MOD

            # 处理上升的情况
            else:
                for j in range(i + 1):
                    for k in range(0, j + 1):
                        dp2[k] = (dp2[k] + dp1[j]) % self._MOD

            dp1 = dp2

        return sum(dp1) % self._MOD


if __name__ == "__main__":
    print(Solution().numPermsDISequence("DID"))  # 5
